package com.zup.algorithm.sort;

import com.zup.algorithm.util.SortUtils;

import java.util.Arrays;

/**
 * 说明：插入排序
 *
 * @author Created by xujinyan on 2018/5/14.
 */
public class InsertSort {
    public static void sort(int[] arr) {
        // 需要排序的元素下标
        for (int i=1; i<arr.length; i++) {
            // 对下表为i的元素往前比较并插入
            int insertIndex = i;
            // 如果需要插入的元素比前面的元素小，则进行交换
            for (int j=i; j>0 && arr[insertIndex] < arr[j-1]; j--) {
                SortUtils.swap(arr, insertIndex, j-1);
                // 将需要插入的元素进行更新
                insertIndex = j-1;
            }
        }
    }

    public static void sortImprove(int[] arr) {
        // 需要排序的元素下标
        for (int i=1; i<arr.length; i++) {
            // 对下表为i的元素往前比较并插入
            int insertIndex = i;
            int insertValue = arr[insertIndex];
            // 如果需要插入的元素比前面的元素小，则进行交换
            for (; insertIndex>0 && insertValue < arr[insertIndex-1]; insertIndex--) {
                // 将需要插入的元素进行更新
                arr[insertIndex] = arr[insertIndex-1];
            }
            arr[insertIndex] = insertValue;
        }
    }

    public static void main(String[] args) {
        int[] arr = SortUtils.generateArr(10, 10);
        InsertSort.sortImprove(arr);
        System.out.println(Arrays.toString(arr));
    }
}
